package g

/*
 * @lc app=leetcode.cn id=70 lang=golang
 *
 * [70] 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
1 <= n <= 45
*/

// @lc code=start
func climbStairs(n int) int {
	return climbStairsNoRecursion(n)
}

// f[i] = f[i-1] + f[i-2]
func climbStairsDB(n int) int {
	if n == 1 {
		return 1
	} else if n == 2 {
		return 2
	} else {
		return climbStairsDB(n-1) + climbStairsDB(n-2)
	}
}

func climbStairsNoRecursion(n int) int {
	count := 0
	if n == 1 {
		count = 1
	} else {
		n1 := 1
		n2 := 2
		for i := 0; i < n-2; i++ {
			n1, n2 = n2, n1+n2
		}
		count = n2
	}
	return count
}

// @lc code=end
